For Time Domain Multiple Access (TDMA) wireless communications systems, an important problem is to mitigate intersymbol interference (ISI) caused when data is transmitted on a dispersive channel with accompanying background noise. This problem is different depending upon what type of air interface is employed. In a second generation system such as the global system for mobile communications (GSM) it suffices to treat the ISI problem in ways that are not adequate for third generation air interfaces such as EDGE (enhanced data rates for GSM evolution). In GSM, optimum performance in terms of error probability is typically accomplished by maximum likelihood sequence estimation (MLSE), but MLSE detection cannot be used to perform optimal equalization in EDGE, due to changes in both the modulation and the channel coding.
When discrete pulses or bursts of information are transmitted through a dispersive medium, they travel over multiple propagation paths to the receiver, and the information transmitted to the receiver will appear smeared. These multipath effects commonly result when signals are reflected to the receiver. The process implemented on the received signal to mitigate ISI is known as “equalization.” This equalization process estimates the individual data symbols which were originally transmitted.
Various approaches have been taken to the equalization problem; linear equalization and decision-feedback equalization (DFE) are two common equalization strategies. However, DFE has poor performance in weak channel coding schemes, such as EDGE transmission modes MCS8–9. A somewhat better approach has been based on MLSE, using the well-known Viterbi algorithm, although this approach ahs drawbacks as explained below. See Shah (U.S. Pat. No. 6,134,277); Cooper (U.S. Pat. No. 5,502,735).
Those skilled in the art will understand that a communication channel behaves in many respects like a filter, and therefore ISI itself may be modelled as a filter. The length of the filter is the extent of ISI, and this length may be referred to as the impulse response length L. Unlike DFE, MLSE detection typically uses trellis diagrams which show a progression of states with the passage of time, and the number of states S is given by M to the power of L−1 (i.e. S=ML−1) where M is the number of symbol levels in the data alphabet used. Consequently, for large response lengths and large alphabet sizes, the equalizer implementation becomes immensely complex. The complexity of the Viterbi Algorithm increases exponentially with channel length, and therefore implementation of the full Viterbi Algorithm becomes unacceptably complex in EDGE. Thus, MLSE using the full Viterbi algorithm is inadequate, and a sub-optimal equalizer capable of performance comparable to that of MLSE is necessary, with acceptable low complexity.
A well-known sub-optimal type of equalizer employs Reduced State Sequence Estimation (RSSE), wherein a reduced-state maximum likelihood (ML) trellis uses set partitioning and decision feedback techniques. See, for example, “Reduced-State Sequence Estimation With Set Partitioning and Decision Feedback” by M. Eyuboglu, and S. Qureshi, IEEE Trans. Comm., vol. 36, pp. 12–20, January 1988. A particularly useful special case of RSSE is Delayed Decision Feedback Sequence Estimation (DFSE). A precondition for applying RSSE is that the input signal is of minimum phase (i.e. the impulse response power decays in time), and this condition can be satisfied by applying prefiltering to the received signal, for example using a DFE feedforward filter.
Additional equalization reliability measures are helpful in order to improve channel decoding subsequent to equalization, and for this purpose it is desirable to generate soft-output information. Soft bits contain important reliability information that greatly aids the decoder located within the receiver downstream from the equalizer.
Soft-output information can be produced by an algorithm called symbol-by-symbol Maximum A Posteriori (MAP) decoding, which can calculate the probability of each symbol given the whole sequence that has been received. For example, see “Reduced State Soft-Output Trellis-Equalization Incorporating Soft Feedback,” by Müller et al., Proc. IEEE GLOBECOM '96, November 1996. A max-log-MAP algorithm is familiar to persons skilled in the art as a simplified version of a MAP algorithm, and max-log-MAP equalizers operate in a logarithmic domain as compared to a probability domain. Another known method for producing soft-output information is using decision feedback partial sequence estimation (DFPSE). DFPSE equalizers are equalizers which employ a non-zero delay reduced state trellis calculation and which achieve reduction of implementation complexity by (1) employing decision feedback, (2) relying on improved accuracy of initial symbol detection which reduces the scope of searching, and (3) using ML or Max-log-MAP detection criteria. DFPSE is also known as block decision feedback equalization. See “Block Decision Feedback Equalization” by Williamson et al., IEEE Trans Comm., vol. 40, pp. 255–264, February 1992. As will be understood by those of ordinary skill in the art, non-zero delay refers to the those situations in which, after a signal is received, there must be a waiting period before soft bits are computed, and this may be due to the need to examine more than one received symbol.
Although using a reduced number of states “S” (e.g. via RSSE or DFPSE) produces very good hard symbol decisions with extremely low complexity, problems arise in producing soft decisions (i.e. soft bits) such as log likelihood ratios or bit probabilities of transmitted bits. A familiar response to these problems is to use trellis truncation, but trellis truncation in and of itself does not allow calculation of MAP or MLSE soft decisions for all bits of a symbol. In other words, when the number of states in the equalizer is reduced to obtain an acceptably low complexity, computing soft bits for all of the bits becomes problematic according to existing methods.
The total number of states in a subset trellis is given by the product of the Jk and each Jk ranges from 1 to M. So, the minimum number of states for an equalizer would be 1 for J={1,1,1 . . . 1} which actually corresponds to DFE. At the other extreme is full MAP or MLSE in which case J={J1, J2, J3 . . . Jl−1} and Jj=M and thus the number of states would be Ml−1 as discussed above. Recall that “l” is impulse response length, and also bear in mind that the Jk are subject to a constraint J1≧J2≧J3≧ . . . Jl−1. For an equalizer having J={J1, J2, J3 . . . JK−1, 1, 1 . . . 1} where K≦L and Ji<M the hard decision performance remains extremely good, but calculation of adequate soft decisions is difficult. Therefore, a need exists to increase reliable performance of low complexity equalizers, especially for high order modulations, by more fully and successfully producing soft bit information.
In general, EDGE systems involve capture of 2 or 3 taps in the MAP or MLSE part of the equalizer, and this means 8 or 64 states respectively for existing DFSE equalizers, or alternatively 4 or 16 states respectively for existing RSSE/RS-MAP equalizers with 4-way set partitioning. Digital signal processing (DSP) implementation of the simplest 4-state equalizer currently requires some 32 million instructions per second (MIPS) per time slot for EDGE at 8 PSK (phase shift keying). In order to provide higher data rate, it is desirable to have lower complexity algorithms than are currently available, or else DSP will be too costly. Although 2-way set partitioning with RSSE or RS-MAP is a candidate for achieving lower complexity, it entails problematic soft bit computation. Likewise, soft symbol equalization is a candidate for replacing soft bit equalization, but soft symbol equalization is approximately 1.5 dB worse than soft bit equalization for 8 PSK EDGE, and this situation gets even worse for higher order modulations using current technology.